package basic.sort.greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.greedy
 * @since JDK1.8
 *
 * 输入: 正数数组costs、正数数组profits、正数K、正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做k个项目
 * M表示你初始的资金
 * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 输出：你最后获得的最大钱数。
 */
public class IPO {

    private static class Program {
        public int p;
        public int c;

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    /**
     *
     * @param k 表示你只能串行的最多做k个项目
     * @param w 表示你初始的资金
     * @param profits 表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @param capital 表示i号项目的花费
     * @return 你最后获得的最大钱数。
     */
    private static int greedy(int k, int w, int[] profits, int[] capital) {
        // 两个堆，一个按花费排序，一个按利润排序
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());

        // 将所有项目添加到花费堆中
        for (int i = 0; i < capital.length; i++) {
            minCostQ.add(new Program(profits[i], capital[i]));
        }

        // 循环做项目
        for (int i = 0; i < k; ++i) {
            // 将项目中此时花费比此时启动资金小的项目全部添加到利润堆中
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) {
                maxProfitQ.add(minCostQ.poll());
            }

            // 判断此时利润堆是否为空
            if (!maxProfitQ.isEmpty()) {
                // 不为空则添加此时最大利润
                w += maxProfitQ.poll().p;
            } else {
                // 为空则直接返回最大钱数
                return w;
            }
        }

        return w;
    }

    private static class MinCostComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c;
        }
    }

    private static class MaxProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;
        }
    }
}
